package demo1;

import java.util.List;

public class MySingleList {
    static class ListNode {//内部类
        public int val;
        public ListNode next;//null

        public ListNode(int val) {//构造方法
            this.val = val;
        }
    }

    public ListNode head;//永远指向头节点

    public void creatList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);//默认就是空
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
    }

    //遍历单链表
    public void show(){
        //这里不是定义了一个节点，只是一个引用
        ListNode cur = head;//引用变量
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    //指定位置打印
    //重载
    public void show(ListNode newHead){
        //这里不是定义了一个节点，只是一个引用
        ListNode cur = newHead;//引用变量
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    //得到单链表的长度
    //列表中节点的个数
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }


    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur!=null){
            //如果val的值是引用类型，那么这里用equals来进行比较！！！
            if (cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }


    //头插法
    public void addFirst(int data){
        //定义一个新的节点
        //没有节点的情况下，验证依然成立
        ListNode node = new ListNode(data);
        node.next=head;
        head = node;
    }


    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if (head==null){
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next!=null){
            cur=cur.next;
        }
        //cur指向的节点是尾巴节点
        cur.next = node;
    }


    //任意位置插入，第一个数据节点为0下标
    public void addIndex(int index,int data){
        int len = size();
        //0.判断index位置的合法性
        if (index < 0|| index > len){
            throw new IndexOutOfBounds("位置不合格"+index);
        }
        if (index==0){
            addFirst(data);
            return;
        }
        if (index==len){
            addLast(data);
            return;
        }
        //1.先找到index-1位置的节点
        ListNode cur = findIndex(index);
        //2.进行插入
        ListNode node = new ListNode(data);
        node.next=cur.next;
        cur.next=node;
    }

    //找到index-1位置的节点
    private ListNode findIndex(int index){
        ListNode cur = head;
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;//index-1的节点
    }

    //删除第一次出现关键字key的节点
    public void remove(int key){
        if (head==null){
            return;
        }
        //删除的是头节点
        if (head.val==key){
            head = head.next;
            return;
        }
        ListNode prev = searchPrev(key);
        if (prev==null){
            System.out.println("没有这个数");
            return;
        }
        ListNode del = prev.next;
        prev.next = del.next;

    }

    private ListNode searchPrev(int key){
        ListNode prev = head;
        while (prev.next!=null){
            if (prev.next.val==key){
                return prev;
            }else {
                prev = prev.next;
            }
        }
        return null;
    }

    //删除所有的关键字key，要求只遍历链表一遍，时间复杂度为O（N）
    public void removeAllkay(int key){
        if (head==null){
            return;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while (cur!= null){
            if (cur.val == key){
                prev.next = cur.next;
                cur=cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val==key){
            head=head.next;
        }
    }

    //每个节点都被回收
    public void clear(){
        /*this.head=null;*/
        while (head!=null){
            ListNode headNext = head.next;
            head.next = null;
            head = headNext;
        }
    }


    //反转单链表
    public ListNode reverseList() {//返回值返回新的头节点
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode cur = head.next;
        head.next=null;
        while(cur!=null){
            ListNode curnext = cur.next;
            cur.next= head;
            head = cur;
            cur=curnext;
        }
        return head;
    }

    //返回链表的中间节点
    public ListNode middleNode() {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode fast =head;
        ListNode slow =head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }


    //返回倒数第k个节点
    public ListNode FindKthToTail(int k) {
        if(k<=0||head==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        //1.先让fast走k-1
        for (int i = 0; i<k-1;i++){
            fast=fast.next;
            if (fast==null){
                return null;
            }
        }
        //2.同时走，走到fast.next=null，返回slow
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    //合并两个有序链表
    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2)
    {
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;
        while (list1!=null && list2!=null){
            if (list1.val < list2.val){
                tmp.next = list1;
                tmp = tmp.next;
                list1 = list1.next;
            }else {
                tmp.next = list2;
                tmp = tmp.next;
                list2 = list2.next;
            }
        }
        if (list1!=null){
            tmp.next = list1;
        }
        if (list2!=null){
            tmp.next=list2;
        }
        return newHead.next;
    }


    //链表分割
    public ListNode partition(int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;

        while (cur != null){
            if (cur.val < x){
                if (bs == null){
                    bs = cur;
                    be = cur;
                    //cur = cur.next;
                }else {
                    be.next = cur;
                    be = be.next;//be = cur;
                    //cur = cur.next;省略1
                }
                //cur = cur.next;省略2
            }else {
                if (as == null){
                    //第一次插入
                    as = cur;
                    ae = cur;
                    //cur = cur.next;
                }else {
                    ae.next = cur;
                    ae = cur;
                    //cur = cur.next;
                }
                //cur = cur.next;
            }
            cur = cur.next;
        }
        //难道两个段都有数据嘛
        //第一个段没有数据，直接返回第二个段
        if (bs==null){
            return as;
        }
        be.next=as;
        if (as!=null){
            ae.next = null;
        }
        return bs;
    }


    //链表的回文结构
    public boolean chkPalindrome(){
        if (head==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast!= null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow所指的位置就是中间节点
        //2.开始翻转
        ListNode cur = slow.next;
        while (cur!=null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //此时翻转完成
        //3.判断
        while (head!=slow){
            if (head.val != slow.val){
                return false;
            }
            //针对偶数节点
            if (head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }


    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(23);
        mySingleList1.addLast(34);
        mySingleList1.addLast(45);
        mySingleList1.addLast(56);

        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(12);
        mySingleList2.addLast(25);
        mySingleList2.addLast(34);
        mySingleList2.addLast(55);
        mySingleList2.addLast(96);
        MySingleList.ListNode ret= mergeTwoLists(mySingleList1.head,mySingleList2.head);

        mySingleList1.show(ret);
    }
}
